article

Colouring Clique-Hypergraphs of Circulant Graphs

Authors:

C. P. MelloAuthors Info & Claims

Graphs and Combinatorics, Volume 29, Issue 6

Pages 1713 - 1720

https://doi.org/10.1007/s00373-012-1241-4

Published: 01 November 2013 Publication History

Abstract

A clique-colouring of a graph G is a colouring of the vertices of G so that no maximal clique of size at least two is monochromatic. The clique-hypergraph, $${\mathcal{H}(G)}$$ , of a graph G has V ( G ) as its set of vertices and the maximal cliques of G as its hyperedges. A vertex-colouring of $${\mathcal{H}(G)}$$ is a clique-colouring of G . Determining the clique-chromatic number, the least number of colours for which a graph G admits a clique-colouring, is known to be NP -hard. In this work, we establish that the clique-chromatic number of powers of cycles is equal to two, except for odd cycles of size at least five, that need three colours. For odd-seq circulant graphs, we show that their clique-chromatic number is at most four, and determine the cases when it is equal to two. Similar bounds for the chromatic number of these graphs are also obtained.

References

[1]

Bacs¿ G., Gravier S., Gyárfás A., Preissmann M., Seb¿ A.: Coloring the maximal cliques of graphs. SIAM J. Discrete Math. 17(3), 361---376 (2004)

Digital Library

[2]

Bermond J.C., Peyrat C.: Induced subgraphs of the power of a cycle. SIAM Discrete Math. J. 2(4), 452---455 (1989)

Digital Library

[3]

Bondy J.A., Locke S.C.: Triangle-free subgraphs of powers of cycles. Graphs Combin. 8(2), 109---118 (1992)

Digital Library

[4]

Brandstädt A., Dragan F.F., Nicolai F.: LexBFS-orderings and powers of chordal graphs. Discrete Math. 171, 27---42 (1997)

Digital Library

[5]

Brown J., Hoshino R.: Independence polynomials of circulants with an application to music. Discrete Math. 309(8), 2292---2304 (2009)

Digital Library

[6]

Campos C.N., de Mello C.P.: A result on the total colouring of powers of cycles. Discrete Appl. Math. 155(5), 585---597 (2007)

Digital Library

[7]

Chebikin D.: Graph powers and k-ordered Hamiltonicity. Discrete Math. 308(15), 3220---3229 (2008)

Digital Library

[8]

Chudnovsky, M., Robertson, N., Seymour, P., Thomas R.: The strong perfect graph theorem. Ann. Math. (2) 164(1), 51---229 (2006)

[9]

Codenotti B., Gerace I., Vigna S.: Hardness results and spectral techniques for combinatorial problems on circulant graphs. Linear Algebra Appl. 285, 123---142 (1998)

[10]

Défossez D.: Clique-coloring some classes of odd-hole-free graphs. J. Graph Theory 53(3), 233---249 (2006)

Digital Library

[11]

Défossez D.: Complexity of clique-coloring odd-hole-free graphs. J. Graph Theory 62(2), 139---156 (2009)

Digital Library

[12]

Duffus D., Sands B., Sauer N., Woodrow R.E.: Two-colouring all two-element maximal antichains. J. Combin. Theory Ser. A 57(1), 109---116 (1991)

Digital Library

[13]

Gravier S., Hoàng C.T., Maffray F.: Coloring the hypergraph of maximal cliques of a graph with no long path. Discrete Math. 272, 285---290 (2003)

Digital Library

[14]

Heuberger C.: On planarity and colorability of circulant graphs. Discrete Math. 268, 153---169 (2003)

Digital Library

[15]

Kratochvíl J., Tuza Z.: On the complexity of bicoloring clique hypergraphs of graphs. J. Algorithms 45(1), 40---54 (2002)

Digital Library

[16]

Krivelevich M., Nachmias A.: Colouring powers of cycles from random lists. Eur. J. Combin. 25(7), 961---968 (2004)

Digital Library

[17]

Li D., Liu M.: Hadwiger's conjecture for powers of cycles and their complements. Eur. J. Combin. 28(4), 1152---1155 (2007)

Digital Library

[18]

Lin C., Lin J.J., Shyu T.W.: Isomorphic star decompositions of multicrowns and the power of cycles. Ars Combin. 53, 249---256 (1999)

[19]

Locke S.C.: Further notes on: largest triangle-free subgraphs in powers of cycles. Ars Combin. 49, 65---77 (1998)

[20]

Meidanis, J.: Edge coloring of cycle powers is easy (1998). http://www.ic.unicamp.br/~meidanis/. Unpublished manuscript, last visited 09/12/2012

[21]

Muzychuk, M.E., Tinhofer, G.: Recognizing circulant graphs of prime order in polynomial time. Electron. J. Combin. 5, Research Paper 25, 28 (1998)

[22]

Mycielski J.: Sur le coloriage des graphs. Colloq. Math. 3, 161---162 (1955)

[23]

Obradović N., Peters J., Ru¿ić G.: Minimum chromaticity of circulant graphs. Discrete Math. 299, 288---296 (2005)

Digital Library

[24]

Obradović N., Peters J., Ru¿ić G.: Efficient domination in circulant graphs with two chord lengths. Inform. Process. Lett. 102(6), 253---258 (2007)

Digital Library

[25]

Oriolo, G., Stauffer, G.: Clique-circulants and the stable set polytope of fuzzy circular interval graphs. Math. Program. 115(2, Ser. A), 291---317 (2008)

[26]

Parsons T.D.: Circulant graph imbeddings. J. Combin. Theory Ser. B. 29(3), 310---320 (1980)

[27]

Prowse A., Woodall D.R.: Choosability of powers of circuits. Graphs Combin. 19(1), 137---144 (2003)

[28]

Thomassen C.: Some remarks on Hajós' conjecture. J. Combin. Theory Ser. B. 93(1), 95---105 (2005)

Digital Library

[29]

Valencia-Pabon M., Vera J.: Independence and coloring properties of direct products of some vertex-transitive graphs. Discrete Math. 306(18), 2275---2281 (2006)

Digital Library

Cited By

(2017)Clique coloring B1-EPG graphsDiscrete Mathematics10.1016/j.disc.2017.01.019340:5(1008-1011)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.disc.2017.01.019
Liang ZShan EZhang Y(2017)A linear-time algorithm for clique-coloring problem in circular-arc graphsJournal of Combinatorial Optimization10.1007/s10878-015-9941-333:1(147-155)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s10878-015-9941-3
(2015)Coloring clique-hypergraphs of graphs with no subdivision of K 5Theoretical Computer Science10.1016/j.tcs.2015.05.030592:C(166-175)Online publication date: 9-Aug-2015
https://dl.acm.org/doi/10.1016/j.tcs.2015.05.030
Show More Cited By

Colouring Clique-Hypergraphs of Circulant Graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
    2. Graph theory
2. Theory of computation

Recommendations

Clique-Colouring and biclique-colouring unichord-free graphs
LATIN'12: Proceedings of the 10th Latin American international conference on Theoretical Informatics

The class of unichord-free graphs was recently investigated in the context of vertex-colouring [J. Graph Theory 63 (2010) 31---67], edge-colouring [Theoret. Comput. Sci. 411 (2010) 1221---1234] and total-colouring [Discrete Appl. Math. 159 (2011) 1851---...
Efficient Algorithms for Clique-Colouring and Biclique-Colouring Unichord-Free Graphs

The class of unichord-free graphs was recently investigated in the context of vertex-colouring (Trotignon and Vušković in J Graph Theory 63(1): 31---67, 2010), edge-colouring (Machado et al. in Theor Comput Sci 411(7---9): 1221---1234, 2010) and total-...
Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3

A clique of a graph is a maximal set of vertices of size at least 2 that induces a complete graph. A k-clique-colouring of a graph is a colouring of the vertices with at most k colours such that no clique is monochromatic. Défossez proved that the 2-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Graphs and Combinatorics

Graphs and Combinatorics Volume 29, Issue 6

November 2013

399 pages

ISSN:0911-0119

EISSN:1435-5914

Issue’s Table of Contents

Copyright © Copyright © 2013 Springer Japan.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 November 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

(2017)Clique coloring B1-EPG graphsDiscrete Mathematics10.1016/j.disc.2017.01.019340:5(1008-1011)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.disc.2017.01.019
Liang ZShan EZhang Y(2017)A linear-time algorithm for clique-coloring problem in circular-arc graphsJournal of Combinatorial Optimization10.1007/s10878-015-9941-333:1(147-155)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s10878-015-9941-3
(2015)Coloring clique-hypergraphs of graphs with no subdivision of K 5Theoretical Computer Science10.1016/j.tcs.2015.05.030592:C(166-175)Online publication date: 9-Aug-2015
https://dl.acm.org/doi/10.1016/j.tcs.2015.05.030
Macêdo Filho HDantas SMachado RFigueiredo C(2015)Biclique-colouring verification complexity and biclique-colouring power graphsDiscrete Applied Mathematics10.1016/j.dam.2014.05.001192:C(65-76)Online publication date: 10-Sep-2015
https://dl.acm.org/doi/10.1016/j.dam.2014.05.001

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents