Results 11 to 20 of about 4,514 (260)
Balancedness of subclasses of circular-arc graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2014 Graph Theory A graph is balanced if its clique-vertex incidence matrix contains no square submatrix of odd order with exactly two ones per row and per column. There is a characterization of balanced graphs by forbidden induced subgraphs, but no characterization by mininal forbidden induced subgraphs is known, not even for the case of circular-
Flavia Bonomo +3 more
openaire +7 more sources
On coherent configuration of circular-arc graphs [PDF]
Communications in Combinatorics and OptimizationFor any graph, Weisfeiler and Leman assigned the smallest matrix algebra which contains the adjacency matrix of the graph. The coherent configuration underlying this algebra for a graph $\Gamma$ is called the coherent configuration of $\Gamma ...
Fatemeh Raei Barandagh +1 more
doaj +2 more sources
Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
Discrete Applied Mathematics, 2006 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Haim Kaplan, Yahav Nussbaum
openaire +3 more sources
Pathwidth of Circular-Arc Graphs [PDF]
, 2007 The pathwidth of a graph G is the minimum clique number of H minus one, over all interval supergraphs H of G. Although pathwidth is a well-known and well-studied graph parameter, there are extremely few graph classes for which pathwidh is known to be tractable in polynomial time.
Karol Suchan, Ioan Todinca
openaire +2 more sources
Partial Characterizations of Circular-Arc Graphs
Electronic Notes in Discrete Mathematics, 2008 AbstractA circular‐arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular‐arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to ...
Flavia Bonomo +3 more
openaire +6 more sources
On cliques of Helly Circular-arc Graphs
Electronic Notes in Discrete Mathematics, 2008 Abstract A circular-arc graph is the intersection graph of a set of arcs on the circle. It is a Helly circular-arc graph if it has a Helly model, where every maximal clique is the set of arcs that traverse some clique point on the circle. A clique model is a Helly model that identifies one clique point for each maximal clique.
Min Chih Lin +3 more
openaire +2 more sources
Hadwiger’s conjecture for proper circular arc graphs
European Journal of Combinatorics, 2009 18 pages, 2 ...
Naveen Belkale, L. Sunil Chandran
openaire +4 more sources
Essential obstacles to Helly circular-arc graphs
, 2022 A Helly circular-arc graph is the intersection graph of a set of arcs on a circle having the Helly property. We introduce essential obstacles, which are a refinement of the notion of obstacles, and prove that essential obstacles are precisely the minimal
Safe, Martin Dario
core +1 more source
Power Domination in Circular-Arc Graphs [PDF]
Algorithmica, 2011 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Chung-Shou Liao, D. T. Lee
openaire +1 more source
Description of shape patterns using circular arcs for object detection
IET Computer Vision, 2013 The authors propose a novel object detection algorithm based on shape matching using a single sketch of an object. The proposed algorithm uses circular arc segments to describe image edges; this approach is advantageous for shape description, shape ...
Wonil Chang, Soo‐Young Lee
doaj +1 more source