Join colourings of chordal graphs

We consider certain partition problems typified by the following two questions. When is a given graph the join of two k-colourable graphs? When is a given graph the join of a k-colourable graph and a graph whose complement is k-colourable? We focus on the class of chordal graphs, and employ the lang...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2015-12, Vol.338 (12), p.2453-2461
Main Authors: Hell, Pavol, Yen, Pei-Lan
Format: Article
Language:English
Subjects:
Algorithms
Chordal graph
Colouring
Complement
Forbidden subgraph characterization
Graph homomorphism
Graph partition
Graphs
Mathematical analysis
Obstructions
Partitions
Recognition
Split graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c333t-917556dc80e52e404e9de27fc507b612d034f6f793a77c16832778d62ce7d6da3
cites cdi_FETCH-LOGICAL-c333t-917556dc80e52e404e9de27fc507b612d034f6f793a77c16832778d62ce7d6da3
container_end_page 2461
container_issue 12
container_start_page 2453
container_title Discrete mathematics
container_volume 338
creator Hell, Pavol
Yen, Pei-Lan
description We consider certain partition problems typified by the following two questions. When is a given graph the join of two k-colourable graphs? When is a given graph the join of a k-colourable graph and a graph whose complement is k-colourable? We focus on the class of chordal graphs, and employ the language of matrix partitions. Our emphasis is on forbidden induced subgraph characterizations. We describe all chordal minimal obstructions to the existence of such partitions; they are surprisingly small and regular. We also give another characterization which yields a more efficient recognition algorithm. By contrast, most of these partition problems are NP-complete if chordality is not assumed.
doi_str_mv 10.1016/j.disc.2015.06.005
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_1718938691</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S0012365X15002290</els_id><sourcerecordid>1718938691</sourcerecordid><originalsourceid>FETCH-LOGICAL-c333t-917556dc80e52e404e9de27fc507b612d034f6f793a77c16832778d62ce7d6da3</originalsourceid><addsrcrecordid>eNp9kE1LAzEURYMoWKt_wNW4czPje0knyYAbKdYPCm4UugsxedOmTCc1aQX_vVPq2tXjwT0X7mHsGqFCQHm3rnzIruKAdQWyAqhP2Ai14qXUuDhlIwDkpZD14pxd5LyG4ZdCj9jNawx94WIX9yn0y1zEtnCrmLztimWy21W-ZGet7TJd_d0x-5g9vk-fy_nb08v0YV46IcSubFDVtfROA9WcJjChxhNXratBfUrkHsSkla1qhFXKodSCK6W95I6Ul96KMbs99m5T_NpT3pnNMIm6zvYU99mgQt0ILRscovwYdSnmnKg12xQ2Nv0YBHPwYdbm4MMcfBiQZvAxQPdHiIYR34GSyS5Q78iHRG5nfAz_4b_c1GdJ</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1718938691</pqid></control><display><type>article</type><title>Join colourings of chordal graphs</title><source>ScienceDirect Freedom Collection 2022-2024</source><creator>Hell, Pavol ; Yen, Pei-Lan</creator><creatorcontrib>Hell, Pavol ; Yen, Pei-Lan</creatorcontrib><description>We consider certain partition problems typified by the following two questions. When is a given graph the join of two k-colourable graphs? When is a given graph the join of a k-colourable graph and a graph whose complement is k-colourable? We focus on the class of chordal graphs, and employ the language of matrix partitions. Our emphasis is on forbidden induced subgraph characterizations. We describe all chordal minimal obstructions to the existence of such partitions; they are surprisingly small and regular. We also give another characterization which yields a more efficient recognition algorithm. By contrast, most of these partition problems are NP-complete if chordality is not assumed.</description><identifier>ISSN: 0012-365X</identifier><identifier>EISSN: 1872-681X</identifier><identifier>DOI: 10.1016/j.disc.2015.06.005</identifier><language>eng</language><publisher>Elsevier B.V</publisher><subject>Algorithms ; Chordal graph ; Colouring ; Complement ; Forbidden subgraph characterization ; Graph homomorphism ; Graph partition ; Graphs ; Mathematical analysis ; Obstructions ; Partitions ; Recognition ; Split graph</subject><ispartof>Discrete mathematics, 2015-12, Vol.338 (12), p.2453-2461</ispartof><rights>2015 Elsevier B.V.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c333t-917556dc80e52e404e9de27fc507b612d034f6f793a77c16832778d62ce7d6da3</citedby><cites>FETCH-LOGICAL-c333t-917556dc80e52e404e9de27fc507b612d034f6f793a77c16832778d62ce7d6da3</cites><orcidid>0000-0001-7609-9746</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Hell, Pavol</creatorcontrib><creatorcontrib>Yen, Pei-Lan</creatorcontrib><title>Join colourings of chordal graphs</title><title>Discrete mathematics</title><description>We consider certain partition problems typified by the following two questions. When is a given graph the join of two k-colourable graphs? When is a given graph the join of a k-colourable graph and a graph whose complement is k-colourable? We focus on the class of chordal graphs, and employ the language of matrix partitions. Our emphasis is on forbidden induced subgraph characterizations. We describe all chordal minimal obstructions to the existence of such partitions; they are surprisingly small and regular. We also give another characterization which yields a more efficient recognition algorithm. By contrast, most of these partition problems are NP-complete if chordality is not assumed.</description><subject>Algorithms</subject><subject>Chordal graph</subject><subject>Colouring</subject><subject>Complement</subject><subject>Forbidden subgraph characterization</subject><subject>Graph homomorphism</subject><subject>Graph partition</subject><subject>Graphs</subject><subject>Mathematical analysis</subject><subject>Obstructions</subject><subject>Partitions</subject><subject>Recognition</subject><subject>Split graph</subject><issn>0012-365X</issn><issn>1872-681X</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2015</creationdate><recordtype>article</recordtype><recordid>eNp9kE1LAzEURYMoWKt_wNW4czPje0knyYAbKdYPCm4UugsxedOmTCc1aQX_vVPq2tXjwT0X7mHsGqFCQHm3rnzIruKAdQWyAqhP2Ai14qXUuDhlIwDkpZD14pxd5LyG4ZdCj9jNawx94WIX9yn0y1zEtnCrmLztimWy21W-ZGet7TJd_d0x-5g9vk-fy_nb08v0YV46IcSubFDVtfROA9WcJjChxhNXratBfUrkHsSkla1qhFXKodSCK6W95I6Ul96KMbs99m5T_NpT3pnNMIm6zvYU99mgQt0ILRscovwYdSnmnKg12xQ2Nv0YBHPwYdbm4MMcfBiQZvAxQPdHiIYR34GSyS5Q78iHRG5nfAz_4b_c1GdJ</recordid><startdate>20151206</startdate><enddate>20151206</enddate><creator>Hell, Pavol</creator><creator>Yen, Pei-Lan</creator><general>Elsevier B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><orcidid>https://orcid.org/0000-0001-7609-9746</orcidid></search><sort><creationdate>20151206</creationdate><title>Join colourings of chordal graphs</title><author>Hell, Pavol ; Yen, Pei-Lan</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c333t-917556dc80e52e404e9de27fc507b612d034f6f793a77c16832778d62ce7d6da3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2015</creationdate><topic>Algorithms</topic><topic>Chordal graph</topic><topic>Colouring</topic><topic>Complement</topic><topic>Forbidden subgraph characterization</topic><topic>Graph homomorphism</topic><topic>Graph partition</topic><topic>Graphs</topic><topic>Mathematical analysis</topic><topic>Obstructions</topic><topic>Partitions</topic><topic>Recognition</topic><topic>Split graph</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Hell, Pavol</creatorcontrib><creatorcontrib>Yen, Pei-Lan</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Discrete mathematics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Hell, Pavol</au><au>Yen, Pei-Lan</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Join colourings of chordal graphs</atitle><jtitle>Discrete mathematics</jtitle><date>2015-12-06</date><risdate>2015</risdate><volume>338</volume><issue>12</issue><spage>2453</spage><epage>2461</epage><pages>2453-2461</pages><issn>0012-365X</issn><eissn>1872-681X</eissn><abstract>We consider certain partition problems typified by the following two questions. When is a given graph the join of two k-colourable graphs? When is a given graph the join of a k-colourable graph and a graph whose complement is k-colourable? We focus on the class of chordal graphs, and employ the language of matrix partitions. Our emphasis is on forbidden induced subgraph characterizations. We describe all chordal minimal obstructions to the existence of such partitions; they are surprisingly small and regular. We also give another characterization which yields a more efficient recognition algorithm. By contrast, most of these partition problems are NP-complete if chordality is not assumed.</abstract><pub>Elsevier B.V</pub><doi>10.1016/j.disc.2015.06.005</doi><tpages>9</tpages><orcidid>https://orcid.org/0000-0001-7609-9746</orcidid></addata></record>
fulltext fulltext
identifier ISSN: 0012-365X
ispartof Discrete mathematics, 2015-12, Vol.338 (12), p.2453-2461
issn 0012-365X
1872-681X
language eng
recordid cdi_proquest_miscellaneous_1718938691
source ScienceDirect Freedom Collection 2022-2024
subjects Algorithms
Chordal graph
Colouring
Complement
Forbidden subgraph characterization
Graph homomorphism
Graph partition
Graphs
Mathematical analysis
Obstructions
Partitions
Recognition
Split graph
title Join colourings of chordal graphs
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-06T19%3A33%3A47IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Join%20colourings%20of%20chordal%20graphs&rft.jtitle=Discrete%20mathematics&rft.au=Hell,%20Pavol&rft.date=2015-12-06&rft.volume=338&rft.issue=12&rft.spage=2453&rft.epage=2461&rft.pages=2453-2461&rft.issn=0012-365X&rft.eissn=1872-681X&rft_id=info:doi/10.1016/j.disc.2015.06.005&rft_dat=%3Cproquest_cross%3E1718938691%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c333t-917556dc80e52e404e9de27fc507b612d034f6f793a77c16832778d62ce7d6da3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1718938691&rft_id=info:pmid/&rfr_iscdi=true