On 2-Subcolourings of Chordal Graphs | SpringerLink
Skip to main content
Springer Nature Link
Log in

On 2-Subcolourings of Chordal Graphs

  • Conference paper
LATIN 2008: Theoretical Informatics (LATIN 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4957))

Included in the following conference series:

Abstract

A 2-subcolouring of a graph is a partition of the vertices into two subsets, each inducing a P 3-free graph, i.e., a disjoint union of cliques. We give the first polynomial time algorithm to test whether a chordal graph has a 2-subcolouring. This solves (for two colours) an open problem of Broersma, Fomin, Nešetřil, and Woeginger, who gave an O(n 5) time algorithm for interval graphs. Our algorithm for the larger class of chordal graphs has complexity only O(n 3).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Albertson, M.O., Jamison, R.E., Hedetniemi, S.T., Locke, S.C.: The subchromatic number of a graph. Discrete Mathematics 74, 33–49 (1989)

    Article  MathSciNet  Google Scholar 

  2. Achlioptas, D.: The complexity of G-free colorability. Discrete Mathematics 165/166, 21–30 (1997)

    Article  MathSciNet  Google Scholar 

  3. Fiala, J., Jansen, K., Le, V.B., Seidel, E.: Graph subcoloring: Complexity and algorithms. In: Brandstädt, A., Le, V.B. (eds.) WG 2001. LNCS, vol. 2204, pp. 154–165. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  4. Gimbel, J., Hartman, C.: Subcolorings and the subchromatic number of a graph. Discrete Mathematics 272, 139–154 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  5. Broersma, H., Fomin, F.V., Nešetřil, J., Woeginger, G.J.: More about subcolorings. Computing 69, 187–203 (2002)

    Article  MathSciNet  Google Scholar 

  6. Hell, P., Klein, S., Nogueira, L.T., Protti, F.: Partitioning chordal graphs into independent sets and cliques. Discrete Applied Mathematics 141, 185–194 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  7. Feder, T., Hell, P., Klein, S., Nogueira, L.T., Protti, F.: List matrix partitions of chordal graphs. Theoretical Computer Science 349, 52–66 (2005)

    MATH  MathSciNet  Google Scholar 

  8. Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)

    MATH  Google Scholar 

  9. Spinrad, J.P.: Efficient Graph Representations. American Mathematical Society (2003)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computing Science, Simon Fraser University, 8888 University Drive, Burnaby, B.C., Canada, V5A 1S6

    Juraj Stacho

Authors
  1. Juraj Stacho
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Eduardo Sany Laber Claudson Bornstein Loana Tito Nogueira Luerbio Faria

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Stacho, J. (2008). On 2-Subcolourings of Chordal Graphs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008: Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78773-0_47

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-78773-0_47

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-78772-3

  • Online ISBN: 978-3-540-78773-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation