DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2022.19

Conflict-Free Coloring on Claw-Free Graphs and Interval Graphs

Authors: Sriram Bhyravarapu, Subrahmanyam Kalyanasundaram, and Rogers Mathew

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract

A Conflict-Free Open Neighborhood coloring, abbreviated CFON^* coloring, of a graph G = (V,E) using k colors is an assignment of colors from a set of k colors to a subset of vertices of V(G) such that every vertex sees some color exactly once in its open neighborhood. The minimum k for which G has a CFON^* coloring using k colors is called the CFON^* chromatic number of G, denoted by χ_{ON}^*(G). The analogous notion for closed neighborhood is called CFCN^* coloring and the analogous parameter is denoted by χ_{CN}^*(G). The problem of deciding whether a given graph admits a CFON^* (or CFCN^*) coloring that uses k colors is NP-complete. Below, we describe briefly the main results of this paper. - For k ≥ 3, we show that if G is a K_{1,k}-free graph then χ_{ON}^*(G) = O(k²log Δ), where Δ denotes the maximum degree of G. Dębski and Przybyło in [J. Graph Theory, 2021] had shown that if G is a line graph, then χ_{CN}^*(G) = O(log Δ). As an open question, they had asked if their result could be extended to claw-free (K_{1,3}-free) graphs, which are a superclass of line graphs. Since it is known that the CFCN^* chromatic number of a graph is at most twice its CFON^* chromatic number, our result positively answers the open question posed by Dębski and Przybyło. - We show that if the minimum degree of any vertex in G is Ω(Δ/{log^ε Δ}) for some ε ≥ 0, then χ_{ON}^*(G) = O(log^{1+ε}Δ). This is a generalization of the result given by Dębski and Przybyło in the same paper where they showed that if the minimum degree of any vertex in G is Ω(Δ), then χ_{ON}^*(G)= O(logΔ). - We give a polynomial time algorithm to compute χ_{ON}^*(G) for interval graphs G. This answers in positive the open question posed by Reddy [Theoretical Comp. Science, 2018] to determine whether the CFON^* chromatic number can be computed in polynomial time on interval graphs. - We explore biconvex graphs, a subclass of bipartite graphs and give a polynomial time algorithm to compute their CFON^* chromatic number. This is interesting as Abel et al. [SIDMA, 2018] had shown that it is NP-complete to decide whether a planar bipartite graph G has χ_{ON}^*(G) = k where k ∈ {1, 2, 3}.

Cite as

Sriram Bhyravarapu, Subrahmanyam Kalyanasundaram, and Rogers Mathew. Conflict-Free Coloring on Claw-Free Graphs and Interval Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhyravarapu_et_al:LIPIcs.MFCS.2022.19,
  author =	{Bhyravarapu, Sriram and Kalyanasundaram, Subrahmanyam and Mathew, Rogers},
  title =	{{Conflict-Free Coloring on Claw-Free Graphs and Interval Graphs}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.19},
  URN =		{urn:nbn:de:0030-drops-168173},
  doi =		{10.4230/LIPIcs.MFCS.2022.19},
  annote =	{Keywords: Conflict-free coloring, Interval graphs, Bipartite graphs, Claw-free graphs}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2011.176

Cubicity, Degeneracy, and Crossing Number

Authors: Abhijin Adiga, L. Sunil Chandran, and Rogers Mathew

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract

A k-box B=(R_1,R_2,...,R_k), where each R_i is a closed interval on the real line, is defined to be the Cartesian product R_1 X R_2 X ... X R_k. If each R_i is a unit length interval, we call B a k-cube. Boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is an intersection graph of k-boxes. Similarly, the cubicity of G, denoted as cub(G), is the minimum integer k such that G is an intersection graph of k-cubes. It was shown in [L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan. Representing graphs as the intersection of axis-parallel cubes. MCDES-2008, IISc Centenary Conference, available at CoRR, abs/cs/0607092, 2006.] that, for a graph G with maximum degree \Delta, cub(G) <= \lceil 4(\Delta +1) ln n\rceil. In this paper we show that, for a k-degenerate graph G, cub(G) <= (k+2) \lceil 2e log n \rceil. Since k is at most \Delta and can be much lower, this clearly is a stronger result. We also give an efficient deterministic algorithm that runs in O(n^2k) time to output a 8k(\lceil 2.42 log n\rceil + 1) dimensional cube representation for G. The crossing number of a graph G, denoted as CR(G), is the minimum number of crossing pairs of edges, over all drawings of G in the plane. An important consequence of the above result is that if the crossing number of a graph G is t, then box(G) is O(t^{1/4}{\lceil log t\rceil}^{3/4}) . This bound is tight upto a factor of O((log t)^{3/4}). Let (P,\leq) be a partially ordered set and let G_{P} denote its underlying comparability graph. Let dim(P) denote the poset dimension of P. Another interesting consequence of our result is to show that dim(P) \leq 2(k+2) \lceil 2e \log n \rceil, where k denotes the degeneracy of G_{P}. Also, we get a deterministic algorithm that runs in O(n^2k) time to construct a 16k(\lceil 2.42 log n\rceil + 1) sized realizer for P. As far as we know, though very good upper bounds exist for poset dimension in terms of maximum degree of its underlying comparability graph, no upper bounds in terms of the degeneracy of the underlying comparability graph is seen in the literature.

Cite as

Abhijin Adiga, L. Sunil Chandran, and Rogers Mathew. Cubicity, Degeneracy, and Crossing Number. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 176-190, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{adiga_et_al:LIPIcs.FSTTCS.2011.176,
  author =	{Adiga, Abhijin and Chandran, L. Sunil and Mathew, Rogers},
  title =	{{Cubicity, Degeneracy, and Crossing Number}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{176--190},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.176},
  URN =		{urn:nbn:de:0030-drops-33428},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.176},
  annote =	{Keywords: Degeneracy, Cubicity, Boxicity, Crossing Number, Interval Graph, Intersection Graph, Poset Dimension, Comparability Graph}
}

Search Results

Documents authored by Mathew, Rogers

Conflict-Free Coloring on Claw-Free Graphs and Interval Graphs

Abstract

Cite as

Cubicity, Degeneracy, and Crossing Number

Abstract

Cite as

Thanks for your feedback!

Could not send message