Results 61 to 70 of about 1,168 (127)
Odd chromatic number of graph classes
Journal of Graph Theory, Volume 108, Issue 4, Page 722-744, April 2025.Abstract A graph is called odd (respectively, even) if every vertex has odd (respectively, even) degree. Gallai proved that every graph can be partitioned into two even induced subgraphs, or into an odd and an even induced subgraph. We refer to a partition into odd subgraphs as an odd colouring of G $G$.
Rémy Belmonte +3 more
wiley +1 more source
An efficient g‐centroid location algorithm for cographs
International Journal of Mathematics and Mathematical Sciences, Volume 2005, Issue 9, Page 1405-1413, 2005., 2005 In 1998, Pandu Rangan et al. Proved that locating the g‐centroid for an arbitrary graph is 𝒩𝒫‐hard by reducing the problem of finding the maximum clique size of a graph to the g‐centroid location problem. They have also given an efficient polynomial time algorithm for locating the g‐centroid for maximal outerplanar graphs, Ptolemaic graphs, and split ...
V. Prakash
wiley +1 more source
Siblings of countable cographs
, 2020 We show that every countable cograph has either one or infinitely many siblings. This answers, very partially, a conjecture of Thomass . The main tools are the notion of well quasi ordering and the correspondence between cographs and some labelled ordered trees.
Gena, Hahn +2 more
openaire +3 more sources
The complexity of the perfect matching‐cut problem
Journal of Graph Theory, Volume 108, Issue 3, Page 432-462, March 2025.Abstract PERFECT MATCHING‐CUT is the problem of deciding whether a graph has a perfect matching that contains an edge‐cut. We show that this problem is NP‐complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five‐regular graphs, for graphs of diameter three, and for bipartite graphs of diameter four.
Valentin Bouquet, Christophe Picouleau
wiley +1 more source
Eigenvalue location in cographs [PDF]
Discrete Applied Mathematics, 2018 We give an $O(n)$ time and space algorithm for constructing a diagonal matrix congruent to A+xI, where A is the adjacency matrix of a cograph and $x\in \mathbb{R}$. Applications include determining the number of eigenvalues of a cograph's adjacency matrix that lie in any interval, obtaining a formula for the inertia of a cograph, and exhibiting ...
David P. Jacobs +2 more
openaire +3 more sources
On the Edge‐Density of the Brownian Co‐Graphon and Common Ancestors of Pairs in the CRT
Random Structures &Algorithms, Volume 66, Issue 1, January 2025.ABSTRACT Bassino et al. have shown that uniform random co‐graphs (graphs without induced P4$$ {P}_4 $$) of size n$$ n $$ converge to a certain non‐deterministic graphon. The edge density of this graphon is a random variable Λ∈[0,1]$$ \boldsymbol{\Lambda} \in \left[0,1\right] $$ whose first moments have been computed by these authors.
Guillaume Chapuy
wiley +1 more source
The complexity of dominating set reconfiguration
, 2015 Suppose that we are given two dominating sets $D_s$ and $D_t$ of a graph $G$ whose cardinalities are at most a given threshold $k$. Then, we are asked whether there exists a sequence of dominating sets of $G$ between $D_s$ and $D_t$ such that each ...
A Suzuki +11 more
core +1 more source
Scheduling on uniform machines with a conflict graph: complexity and resolution
International Transactions in Operational Research, Volume 31, Issue 2, Page 863-888, March 2024.Abstract This paper deals with the problem of scheduling a set of unit‐time jobs on a set of uniform machines. The jobs are subject to conflict constraints modeled by a graph G called the conflict graph, in which adjacent jobs cannot be processed on a same machine.
Amin Mallek, Mourad Boudhar
wiley +1 more source
An FPT Algorithm for Directed Co-Graph Edge Deletion
AlgorithmsIn the directed co-graph edge-deletion problem, we are given a directed graph and an integer k, and the question is whether we can delete, at most, k edges so that the resulting graph is a directed co-graph. In this paper, we make two minor contributions.
Wenjun Li +3 more
doaj +1 more source
, 2019 Cographs--defined most simply as complete graphs with colored lines--both dualize and generalize ordinary graphs, and promise a comparably wide range of applications. This article introduces them by examples, catalogues, and elementary properties. Any finite cograph may be realized in several ways, including inner products, polynomials, geometrically ...
openaire +2 more sources