NDLI: Efficient Algorithms for Clique-Colouring and Biclique-Colouring Unichord-Free Graphs

Content Provider	Springer Nature Link
Author	Filho, H. B. Macêdo Machado, R. C. S. Figueiredo, C. M. H.
Copyright Year	2016
Abstract	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-colouring (Machado and de Figueiredo in Discrete Appl Math 159(16): 1851–1864, 2011). Unichord-free graphs proved to have a rich structure that can be used to obtain interesting results with respect to the study of the complexity of colouring problems. In particular, several surprising complexity dichotomies of colouring problems are found in subclasses of unichord-free graphs. In the present work, we investigate clique-colouring and biclique-colouring problems restricted to unichord-free graphs. We show that the clique-chromatic number of a unichord-free graph is at most 3, and that the 2-clique-colourable unichord-free graphs are precisely those that are perfect. Moreover, we describe an O(nm)-time algorithm that returns an optimal clique-colouring of a unichord-free graph input. We prove that the biclique-chromatic number of a unichord-free graph is either equal to or one greater than the size of a largest twin set. Moreover, we describe an $$O(n^2m)$$ -time algorithm that returns an optimal biclique-colouring of a unichord-free graph input. The clique-chromatic and the biclique-chromatic numbers are not monotone with respect to induced subgraphs. The biclique-chromatic number presents an extra unexpected difficulty, as it is not the maximum over the biconnected components, which we overcome by considering additionally the star-biclique-chromatic number.
Ending Page	814
Page Count	29
Starting Page	786
File Format	PDF
ISSN	01784617
e-ISSN	14320541
Journal	Algorithmica
Issue Number	3
Volume Number	77
Language	English
Publisher	Springer US
Publisher Date	2016-01-04
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Unichord-free Clique-colouring Decomposition Theory of Computation Coloring of graphs and hypergraphs Computer Systems Organization and Communication Networks Data Structures, Cryptology and Information Theory Algorithms Mathematics of Computing Graph algorithms Hypergraphs Biclique-colouring Algorithm Analysis and Problem Complexity
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Fast 3-coloring Triangle-Free Planar Graphs

3-Colouring AT-Free Graphs in Polynomial Time

Deciding k-Colorability of P 5-Free Graphs in Polynomial Time

An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy

Collective Tree Spanners in Graphs with Bounded Parameters

Practical and Efficient Circle Graph Recognition

The Complexity of the Empire Colouring Problem

Finding Shortest Paths Between Graph Colourings

On Independent Vertex Sets in Subclasses of Apple-Free Graphs

Efficient Algorithms for Clique-Colouring and Biclique-Colouring Unichord-Free Graphs

Similar Documents

Fast 3-coloring Triangle-Free Planar Graphs

3-Colouring AT-Free Graphs in Polynomial Time

Deciding k-Colorability of P 5-Free Graphs in Polynomial Time

An Intersection Model for Multitolerance Graphs: Efficient Algorithms and Hierarchy

Collective Tree Spanners in Graphs with Bounded Parameters

Practical and Efficient Circle Graph Recognition

The Complexity of the Empire Colouring Problem

Finding Shortest Paths Between Graph Colourings

On Independent Vertex Sets in Subclasses of Apple-Free Graphs

Efficient Algorithms for Clique-Colouring and Biclique-Colouring Unichord-Free Graphs