On the 12-representability of induced subgraphs of a grid graph

Joanna N. Chen, Sergey Kitaev

Research output: Contribution to journalArticle

Abstract

The notion of a 12-representable graph was introduced by Jones et al.. This notion generalizes the notions of the much studied permutation graphs and co-interval graphs. It is known that any 12-representable graph is a comparability graph, and also that a tree is 12-representable if and only if it is a double caterpillar. Moreover, Jones et al.\ initiated the study of 12-representability of induced subgraphs of a grid graph, and asked whether it is possible to characterize such graphs. This question in is meant to be about induced subgraphs of a grid graph that consist of squares, which we call square grid graphs. However, an induced subgraph in a grid graph does not have to contain entire squares, and we call such graphs line grid graphs. In this paper we answer the question of Jones et al.\ by providing a complete characterization of $12$-representable square grid graphs in terms of forbidden induced subgraphs. Moreover, we conjecture such a characterization for the line grid graphs and give a number of results towards solving this challenging conjecture. Our results are a major step in the direction of characterization of all 12-representable graphs since beyond our characterization, we also discuss relations between graph labelings and 12-representability, one of the key open questions in the area.
Original languageEnglish
Number of pages22
JournalDiscussiones Mathematicae Graph Theory
Publication statusAccepted/In press - 1 Nov 2019

Fingerprint

Grid Graph
Representability
Induced Subgraph
Graph in graph theory
Line Graph
Labeling
Graph Labeling
Comparability Graph
Permutation Graphs
Forbidden Induced Subgraph
Caterpillar
Interval Graphs
Entire
If and only if
Generalise

Keywords

  • graph representation
  • 12-representable graph
  • grid graph
  • forbidden subgraph
  • square grid graph
  • line grid graph

Cite this

Chen, J. N., & Kitaev, S. (Accepted/In press). On the 12-representability of induced subgraphs of a grid graph. Discussiones Mathematicae Graph Theory.
Chen, Joanna N. ; Kitaev, Sergey. / On the 12-representability of induced subgraphs of a grid graph. In: Discussiones Mathematicae Graph Theory. 2019.
@article{b387bbddabcf48e0a6d053bb8c3ae6e6,
title = "On the 12-representability of induced subgraphs of a grid graph",
abstract = "The notion of a 12-representable graph was introduced by Jones et al.. This notion generalizes the notions of the much studied permutation graphs and co-interval graphs. It is known that any 12-representable graph is a comparability graph, and also that a tree is 12-representable if and only if it is a double caterpillar. Moreover, Jones et al.\ initiated the study of 12-representability of induced subgraphs of a grid graph, and asked whether it is possible to characterize such graphs. This question in is meant to be about induced subgraphs of a grid graph that consist of squares, which we call square grid graphs. However, an induced subgraph in a grid graph does not have to contain entire squares, and we call such graphs line grid graphs. In this paper we answer the question of Jones et al.\ by providing a complete characterization of $12$-representable square grid graphs in terms of forbidden induced subgraphs. Moreover, we conjecture such a characterization for the line grid graphs and give a number of results towards solving this challenging conjecture. Our results are a major step in the direction of characterization of all 12-representable graphs since beyond our characterization, we also discuss relations between graph labelings and 12-representability, one of the key open questions in the area.",
keywords = "graph representation, 12-representable graph, grid graph, forbidden subgraph, square grid graph, line grid graph",
author = "Chen, {Joanna N.} and Sergey Kitaev",
year = "2019",
month = "11",
day = "1",
language = "English",

}

Chen, JN & Kitaev, S 2019, 'On the 12-representability of induced subgraphs of a grid graph', Discussiones Mathematicae Graph Theory.

On the 12-representability of induced subgraphs of a grid graph. / Chen, Joanna N.; Kitaev, Sergey.

In: Discussiones Mathematicae Graph Theory, 01.11.2019.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the 12-representability of induced subgraphs of a grid graph

AU - Chen, Joanna N.

AU - Kitaev, Sergey

PY - 2019/11/1

Y1 - 2019/11/1

N2 - The notion of a 12-representable graph was introduced by Jones et al.. This notion generalizes the notions of the much studied permutation graphs and co-interval graphs. It is known that any 12-representable graph is a comparability graph, and also that a tree is 12-representable if and only if it is a double caterpillar. Moreover, Jones et al.\ initiated the study of 12-representability of induced subgraphs of a grid graph, and asked whether it is possible to characterize such graphs. This question in is meant to be about induced subgraphs of a grid graph that consist of squares, which we call square grid graphs. However, an induced subgraph in a grid graph does not have to contain entire squares, and we call such graphs line grid graphs. In this paper we answer the question of Jones et al.\ by providing a complete characterization of $12$-representable square grid graphs in terms of forbidden induced subgraphs. Moreover, we conjecture such a characterization for the line grid graphs and give a number of results towards solving this challenging conjecture. Our results are a major step in the direction of characterization of all 12-representable graphs since beyond our characterization, we also discuss relations between graph labelings and 12-representability, one of the key open questions in the area.

AB - The notion of a 12-representable graph was introduced by Jones et al.. This notion generalizes the notions of the much studied permutation graphs and co-interval graphs. It is known that any 12-representable graph is a comparability graph, and also that a tree is 12-representable if and only if it is a double caterpillar. Moreover, Jones et al.\ initiated the study of 12-representability of induced subgraphs of a grid graph, and asked whether it is possible to characterize such graphs. This question in is meant to be about induced subgraphs of a grid graph that consist of squares, which we call square grid graphs. However, an induced subgraph in a grid graph does not have to contain entire squares, and we call such graphs line grid graphs. In this paper we answer the question of Jones et al.\ by providing a complete characterization of $12$-representable square grid graphs in terms of forbidden induced subgraphs. Moreover, we conjecture such a characterization for the line grid graphs and give a number of results towards solving this challenging conjecture. Our results are a major step in the direction of characterization of all 12-representable graphs since beyond our characterization, we also discuss relations between graph labelings and 12-representability, one of the key open questions in the area.

KW - graph representation

KW - 12-representable graph

KW - grid graph

KW - forbidden subgraph

KW - square grid graph

KW - line grid graph

UR - https://www.dmgt.uz.zgora.pl/index.php

UR - https://arxiv.org/abs/1911.00408

M3 - Article

ER -

Chen JN, Kitaev S. On the 12-representability of induced subgraphs of a grid graph. Discussiones Mathematicae Graph Theory. 2019 Nov 1.